A challenge facing computer architects, compiler writers, and programmers is to understand the dynamic behavior of a program. A program's performance is directly related to the events that occur while the program is executing. One way to increase program performance is to understand the dynamic behavior of a program and improve costly or frequently occurring portions of that program.
Program paths or traces are sequences of consecutively executed program blocks of instructions. These program paths or traces have provided programmers a window into a program's dynamic behavior by capturing aspects of a program's dynamic control flow, not just its aggregate behavior. Using these paths, programmers, compiler writers, and computer architects are provided with a way to improve performance. Programmers or compilers are able to identify heavily executed paths and tune them so that they perform faster.
Performance of large, complex systems, such as operating system and databases have been improved by identifying heavily executed paths and streamlining them into fast paths. In compilers as well, trace scheduling and, more recently, path-based compilation, demonstrate that program optimization can benefit from a focus on a program's dynamic control flow. Recently designed computer architectures have also directly exploited traces or program flow to enhance instruction caching and execution.
Path profiling measures the frequency and cost of a program's executed paths. It is an essential technique to understand a program's control flow. However, current path profiling techniques normally only capture acyclic paths. Acyclic paths are short parts of a program's execution that, unfortunately, end at loop iteration and procedure boundaries, which are two of the most interesting points in a program's execution. Current techniques for path profiling are useful to programmers, but do not easily describe the program's flow through procedure boundaries and loop iterations. Without tools to conveniently identify expensive interprocedural paths, it is difficult to improve the performance of software.
There is a need for a mechanism that can perform path profiling while overcoming the acyclic and intraprocedural path limitations. There is a need for a mechanism to represent the entire flow control of an execution of a program. There is a need for a mechanism to represent the entire flow control of an execution of a program in a manageable format. There is a need for a mechanism to identify the most important parts of that representation so programmers can concentrate their efforts to improve those parts while providing the greatest benefit.